#include <proc.h>
#include <kmalloc.h>
#include <string.h>
#include <sync.h>
#include <pmm.h>
#include <error.h>
#include <sched.h>
#include <elf.h>
#include <vmm.h>
#include <trap.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

/* ------------- process/thread mechanism design&implementation -------------
(an simplified Linux process/thread mechanism )
introduction:
  ucore implements a simple process/thread mechanism. process contains the independent memory sapce, at least one threads
for execution, the kernel data(for management), processor state (for context switch), files(in lab6), etc. ucore needs to
manage all these details efficiently. In ucore, a thread is just a special kind of process(share process's memory).
------------------------------
process state       :     meaning               -- reason
    PROC_UNINIT     :   uninitialized           -- alloc_proc
    PROC_SLEEPING   :   sleeping                -- try_free_pages, do_wait, do_sleep
    PROC_RUNNABLE   :   runnable(maybe running) -- proc_init, wakeup_proc, 
    PROC_ZOMBIE     :   almost dead             -- do_exit

-----------------------------
process state changing:
                                            
  alloc_proc                                 RUNNING
      +                                   +--<----<--+
      +                                   + proc_run +
      V                                   +-->---->--+ 
PROC_UNINIT -- proc_init/wakeup_proc --> PROC_RUNNABLE -- try_free_pages/do_wait/do_sleep --> PROC_SLEEPING --
                                           A      +                                                           +
                                           |      +--- do_exit --> PROC_ZOMBIE                                +
                                           +                                                                  + 
                                           -----------------------wakeup_proc----------------------------------
-----------------------------
process relations
parent:           proc->parent  (proc is children)
children:         proc->cptr    (proc is parent)
older sibling:    proc->optr    (proc is younger sibling)
younger sibling:  proc->yptr    (proc is older sibling)
-----------------------------
related syscall for process:
SYS_exit        : process exit,                           -->do_exit
SYS_fork        : create child process, dup mm            -->do_fork-->wakeup_proc
SYS_wait        : wait process                            -->do_wait
SYS_exec        : after fork, process execute a program   -->load a program and refresh the mm
SYS_clone       : create child thread                     -->do_fork-->wakeup_proc
SYS_yield       : process flag itself need resecheduling, -- proc->need_sched=1, then scheduler will rescheule this process
SYS_sleep       : process sleep                           -->do_sleep 
SYS_kill        : kill process                            -->do_kill-->proc->flags |= PF_EXITING
                                                                 -->wakeup_proc-->do_wait-->do_exit   
SYS_getpid      : get the process's pid

*/

// the process set's list
list_entry_t proc_list;

#define HASH_SHIFT          10
#define HASH_LIST_SIZE      (1 << HASH_SHIFT)
#define pid_hashfn(x)       (hash32(x, HASH_SHIFT))

// has list for process set based on pid
static list_entry_t hash_list[HASH_LIST_SIZE];

// idle proc
struct proc_struct *idleproc = NULL;
// init proc
struct proc_struct *initproc = NULL;
// current proc
struct proc_struct *current = NULL;

static int nr_process = 0;

void kernel_thread_entry(void);
void forkrets(struct trapframe *tf);
void switch_to(struct context *from, struct context *to);

// alloc_proc - alloc a proc_struct and init all fields of proc_struct
static struct proc_struct *
alloc_proc(void) {
    struct proc_struct *proc = kmalloc(sizeof(struct proc_struct));
    if (proc != NULL) {
    //LAB4:EXERCISE1 YOUR CODE
    /*
     * below fields in proc_struct need to be initialized
     *       enum proc_state state;                      // Process state
     *       int pid;                                    // Process ID
     *       int runs;                                   // the running times of Proces
     *       uintptr_t kstack;                           // Process kernel stack
     *       volatile bool need_resched;                 // bool value: need to be rescheduled to release CPU?
     *       struct proc_struct *parent;                 // the parent process
     *       struct mm_struct *mm;                       // Process's memory management field
     *       struct context context;                     // Switch here to run process
     *       struct trapframe *tf;                       // Trap frame for current interrupt
     *       uintptr_t cr3;                              // CR3 register: the base addr of Page Directroy Table(PDT)
     *       uint32_t flags;                             // Process flag
     *       char name[PROC_NAME_LEN + 1];               // Process name
     */
        proc->state = PROC_UNINIT; // 初始状态为未初始化
        proc->pid = -1;            // 初始进程ID为-1
        proc->runs = 0;            // 初始运行次数为0
        proc->kstack = 0;          // 初始内核栈指针为0
        proc->need_resched = 0;    // 初始不需要重新调度
        proc->parent = NULL;       // 初始父进程指针为NULL
        proc->mm = NULL;           // 初始内存管理结构指针为NULL
        memset(&proc->context, 0, sizeof(struct context));  // 初始化上下文切换信息
        proc->tf = NULL;           // 初始中断陷阱帧指针为NULL
        proc->cr3 = boot_cr3;      // 初始CR3寄存器值为0
        proc->flags = 0;           // 初始进程标志为0
        memset(proc->name, 0, PROC_NAME_LEN);   // 初始进程名称为空字符串
    }
    return proc;
}

// set_proc_name - set the name of proc
/**
 * 设置进程名称
 * 
 * 本函数旨在为进程结构体中的名称字段赋予新的值它首先清空进程名称字段中的现有内容，
 * 然后将新的名称复制到该字段中
 * 
 * @param proc 指向进程结构体的指针，该结构体包含进程的相关信息包括进程名称
 * @param name 指向新的进程名称的字符串
 * 
 * @return 返回指向进程名称的指针，这是在内存中直接修改后的结果
 * 
 * 注意：此函数直接操作传入的进程结构体，对名称字段进行先清空后赋值的操作
 */
char *
set_proc_name(struct proc_struct *proc, const char *name) {
    
    // 清空进程名称字段中的现有内容，以准备存储新的名称
    memset(proc->name, 0, sizeof(proc->name));
    // 将新的名称复制到进程名称字段中
    return memcpy(proc->name, name, PROC_NAME_LEN);
}

// get_proc_name - get the name of proc
char *
get_proc_name(struct proc_struct *proc) {
    static char name[PROC_NAME_LEN + 1];
    memset(name, 0, sizeof(name));
    return memcpy(name, proc->name, PROC_NAME_LEN);
}

// get_pid - alloc a unique pid for process
/**
 * 安全地获取下一个进程ID。
 * 
 * 此函数通过遍历进程列表来寻找一个未被使用的进程ID，以确保新分配的ID不会与现有进程冲突。
 * 它使用静态变量来跟踪最后一个分配的PID和下一个安全PID，以提高效率并避免PID冲突。
 * 
 * @return 返回一个未被使用的进程ID。
 */
static int
get_pid(void) {
    // 确保PID的最大值大于系统中允许的最大进程数，以避免PID不足的情况。
    static_assert(MAX_PID > MAX_PROCESS);
    
    // 定义一个指向进程结构的指针，用于遍历进程列表。
    struct proc_struct *proc;
    // 初始化列表指针，从进程列表的头部开始。
    list_entry_t *list = &proc_list, *le;
    // 定义静态变量，next_safe用于记录下一个安全的PID值，last_pid用于记录上一个分配的PID。
    static int next_safe = MAX_PID, last_pid = MAX_PID;

    // 尝试递增last_pid以查找下一个可用的PID，如果超过最大值则重置为1。
    if (++ last_pid >= MAX_PID) {
        last_pid = 1;
        goto inside;
    }

     // 如果当前的last_pid大于等于next_safe，表示需要重新计算下一个安全的PID。
    if (last_pid >= next_safe) {
    inside:
        next_safe = MAX_PID;
    repeat:
        // 从进程列表的头部开始遍历。
        le = list;
        while ((le = list_next(le)) != list) {

            // 将列表项转换为进程结构。
            proc = le2proc(le, list_link);

        // 如果找到相同PID的进程，表示当前last_pid已被使用，需要继续寻找下一个可用的PID。
            if (proc->pid == last_pid) {
                if (++ last_pid >= next_safe) {
                    if (last_pid >= MAX_PID) {
                        last_pid = 1;
                    }
                    next_safe = MAX_PID;
                    goto repeat;
                }
            }

            // 如果找到一个更大的PID，更新next_safe为当前进程的PID，以确保找到的PID是安全的。
            else if (proc->pid > last_pid && next_safe > proc->pid) {
                next_safe = proc->pid;
            }
        }
    }
    // 返回找到的可用PID。
    return last_pid;
}

// proc_run - make process "proc" running on cpu
// NOTE: before call switch_to, should load  base addr of "proc"'s new PDT
void
proc_run(struct proc_struct *proc) {
    if (proc != current) {
        bool intr_flag;
        struct proc_struct *prev = current, *next = proc;
        local_intr_save(intr_flag);
        {
            current = proc;
            load_esp0(next->kstack + KSTACKSIZE);
            lcr3(next->cr3);
            switch_to(&(prev->context), &(next->context));
        }
        local_intr_restore(intr_flag);
    }
}

// forkret -- the first kernel entry point of a new thread/process
// NOTE: the addr of forkret is setted in copy_thread function
//       after switch_to, the current proc will execute here.
static void
forkret(void) {
    forkrets(current->tf);
}

// hash_proc - add proc into proc hash_list
/**
 * 将进程结构体添加到哈希表中
 * 
 * 当需要在哈希表中添加一个进程时，调用此函数将进程结构体中的哈希链接添加到相应的哈希表链表中
 * 这有助于在需要时快速查找进程
 * 
 * @param proc 指向进程结构体的指针，表示要添加到哈希表的进程
 */
static void
hash_proc(struct proc_struct *proc) {
    // 根据进程的PID计算哈希值，并将进程添加到相应哈希链表的末尾
    list_add(hash_list + pid_hashfn(proc->pid), &(proc->hash_link));
}

// find_proc - find proc frome proc hash_list according to pid
struct proc_struct *
find_proc(int pid) {
    if (0 < pid && pid < MAX_PID) {
        list_entry_t *list = hash_list + pid_hashfn(pid), *le = list;
        while ((le = list_next(le)) != list) {
            struct proc_struct *proc = le2proc(le, hash_link);
            if (proc->pid == pid) {
                return proc;
            }
        }
    }
    return NULL;
}

// kernel_thread - create a kernel thread using "fn" function
// NOTE: the contents of temp trapframe tf will be copied to 
//       proc->tf in do_fork-->copy_thread function
/**
 * 创建一个内核线程
 * 
 * @param fn 指向线程要执行的函数的指针
 * @param arg 传递给fn函数的参数
 * @param clone_flags 克隆标志，用于指定线程创建的细节
 * 
 * @return 返回线程创建的结果，成功则为线程ID，失败则为错误码
 * 
 * 该函数通过设置trapframe来创建一个内核线程，并安排其执行指定的函数fn
 * 使用do_fork函数来进行实际的线程创建操作，创建的线程将共享父线程的虚拟内存
 */
int
kernel_thread(int (*fn)(void *), void *arg, uint32_t clone_flags) {
    // 初始化trapframe结构体，用于描述线程的初始状态
    struct trapframe tf;
    memset(&tf, 0, sizeof(struct trapframe));

    // 设置代码段和数据段寄存器的值，使线程运行在内核态
    tf.tf_cs = KERNEL_CS;
    tf.tf_ds = tf.tf_es = tf.tf_ss = KERNEL_DS;

    // 将要执行的函数fn的地址和参数arg的地址分别放入ebx和edx寄存器
    tf.tf_regs.reg_ebx = (uint32_t)fn;
    tf.tf_regs.reg_edx = (uint32_t)arg;

    // 设置指令指针寄存器eip，使其指向内核线程入口函数kernel_thread_entry
    tf.tf_eip = (uint32_t)kernel_thread_entry;

    // 调用do_fork函数创建新线程，新线程将共享父线程的虚拟内存
    // 并将新线程的初始状态设置为之前准备的trapframe
    return do_fork(clone_flags | CLONE_VM, 0, &tf);
}

// setup_kstack - alloc pages with size KSTACKPAGE as process kernel stack
/**
 * 设置进程的内核栈
 * 
 * @param proc 指向进程结构的指针，用于初始化该进程的内核栈
 * @return 0表示成功，-E_NO_MEM表示内存分配失败
 * 
 * 此函数通过分配一页内存用作进程的内核栈，并将该内存页的虚拟地址设置为进程的内核栈地址
 * 如果内存分配成功，则返回0；如果内存分配失败，则返回-E_NO_MEM
 */
static int
setup_kstack(struct proc_struct *proc) {
    // 分配KSTACKPAGE页内存用作内核栈
    struct Page *page = alloc_pages(KSTACKPAGE);
    if (page != NULL) {
        // 如果内存分配成功，将内存页的虚拟地址设置为进程的内核栈地址
        proc->kstack = (uintptr_t)page2kva(page);
        return 0;
    }
    // 如果内存分配失败，返回错误码
    return -E_NO_MEM;
}

// put_kstack - free the memory space of process kernel stack
static void
put_kstack(struct proc_struct *proc) {
    free_pages(kva2page((void *)(proc->kstack)), KSTACKPAGE);
}

// copy_mm - process "proc" duplicate OR share process "current"'s mm according clone_flags
//         - if clone_flags & CLONE_VM, then "share" ; else "duplicate"
/**
 * 复制内存管理信息到新进程。
 * 
 * 该函数负责将当前进程的内存管理信息复制到新进程中。
 * 它是进程创建的关键部分，确保新进程拥有独立的内存空间。
 * 
 * @param clone_flags 指定如何克隆进程的标志位，影响内存和其他资源的复制方式。
 * @param proc 指向新进程的进程结构体指针，用于存储复制的内存管理信息。
 * 
 * 断言当前进程没有内存管理信息。
 */
static int
copy_mm(uint32_t clone_flags, struct proc_struct *proc) {
    assert(current->mm == NULL);
    /* do nothing in this project */
    return 0;
}

// copy_thread - setup the trapframe on the  process's kernel stack top and
//             - setup the kernel entry point and stack of process
/**
 * 复制当前线程的上下文到新进程。
 * 
 * 该函数初始化新进程的陷阱帧和上下文，使其作为当前线程的子进程执行。主要操作包括设置初始执行环境、栈指针，并启用子进程的中断标志。
 * 
 * @param proc 指向新进程的进程结构体，用于存储初始化后的陷阱帧和上下文信息。
 * @param esp 新进程的栈指针，表示新进程栈的初始位置。
 * @param tf 指向当前线程的陷阱帧结构体，用于将当前线程的执行状态复制到新进程中。
 */
static void
copy_thread(struct proc_struct *proc, uintptr_t esp, struct trapframe *tf) {
    // 初始化新进程的陷阱帧，位于其内核栈的顶部
    proc->tf = (struct trapframe *)(proc->kstack + KSTACKSIZE) - 1;

    // 将当前线程的陷阱帧内容复制到新进程的陷阱帧
    *(proc->tf) = *tf;

    // 设置子进程的返回值为0，表示fork成功
    proc->tf->tf_regs.reg_eax = 0;
    // 设置子进程的栈指针为指定的esp位置
    proc->tf->tf_esp = esp;
     // 启用子进程的中断标志
    proc->tf->tf_eflags |= FL_IF;

    // 设置子进程的初始指令指针为forkret函数的地址
    proc->context.eip = (uintptr_t)forkret;
    // 设置子进程的栈指针为其陷阱帧的地址
    proc->context.esp = (uintptr_t)(proc->tf);
}

/* do_fork -     parent process for a new child process
 * @clone_flags: used to guide how to clone the child process
 * @stack:       the parent's user stack pointer. if stack==0, It means to fork a kernel thread.
 * @tf:          the trapframe info, which will be copied to child process's proc->tf
 */

int
do_fork(uint32_t clone_flags, uintptr_t stack, struct trapframe *tf) {
    int ret = -E_NO_FREE_PROC;
    struct proc_struct *proc;
    if (nr_process >= MAX_PROCESS) {
        goto fork_out;
    }
    ret = -E_NO_MEM;
    //LAB4:EXERCISE2 YOUR CODE
    /*
     * Some Useful MACROs, Functions and DEFINEs, you can use them in below implementation.
     * MACROs or Functions:
     *   alloc_proc:   create a proc struct and init fields (lab4:exercise1)
     *   setup_kstack: alloc pages with size KSTACKPAGE as process kernel stack
     *   copy_mm:      process "proc" duplicate OR share process "current"'s mm according clone_flags
     *                 if clone_flags & CLONE_VM, then "share" ; else "duplicate"
     *   copy_thread:  setup the trapframe on the  process's kernel stack top and
     *                 setup the kernel entry point and stack of process
     *   hash_proc:    add proc into proc hash_list
     *   get_pid:      alloc a unique pid for process
     *   wakeup_proc:  set proc->state = PROC_RUNNABLE
     * VARIABLES:
     *   proc_list:    the process set's list
     *   nr_process:   the number of process set
     */

    //    1. call alloc_proc to allocate a proc_struct
    //    2. call setup_kstack to allocate a kernel stack for child process
    //    3. call copy_mm to dup OR share mm according clone_flag
    //    4. call copy_thread to setup tf & context in proc_struct
    //    5. insert proc_struct into hash_list && proc_list
    //    6. call wakeup_proc to make the new child process RUNNABLE
    //    7. set ret vaule using child proc's pid
    //调用alloc_proc，首先获得一块用户信息块
    if((proc = alloc_proc()) == NULL){
        goto fork_out;
    }

    proc->parent = current;

    //为进程分配一个内核栈
    ret = setup_kstack(proc);
    if (ret != 0) {
        goto bad_fork_cleanup_proc;
    }

    //复制原进程的内存管理信息到新进程
    ret = copy_mm(clone_flags, proc);
    if (ret != 0) {
        goto bad_fork_cleanup_kstack;
    }

    //复制原进程上下文到新进程
    copy_thread(proc, stack, tf);

    bool intr_flag;
    local_intr_save(intr_flag);
    {
        //为新进程分配一个pid
        proc->pid = get_pid();
        //将新进程插入到进程列表
        hash_proc(proc);
        list_add(&proc_list, &(proc->list_link));
        nr_process ++;

    }
    local_intr_restore(intr_flag);
    wakeup_proc(proc);
    ret = proc->pid;
fork_out:
    return ret;

bad_fork_cleanup_kstack:
    put_kstack(proc);
bad_fork_cleanup_proc:
    kfree(proc);
    goto fork_out;
}

// do_exit - called by sys_exit
//   1. call exit_mmap & put_pgdir & mm_destroy to free the almost all memory space of process
//   2. set process' state as PROC_ZOMBIE, then call wakeup_proc(parent) to ask parent reclaim itself.
//   3. call scheduler to switch to other process
int
do_exit(int error_code) {
    panic("process exit!!.\n");
}

// init_main - the second kernel thread used to create user_main kernel threads
/**
 * 初始化主函数，用于初始化进程
 * 
 * @param arg 传递给初始化进程的参数，可以是任意类型，这里被解释为字符串
 * 
 * 此函数主要负责在系统初始化期间执行一些打印操作，以提供有关当前进程的信息
 * 和初始化参数的内容它不进行任何错误处理或复杂逻辑，主要是为了演示和调试目的
 * 
 * @return 返回0，表示初始化成功没有返回值表示失败，因为这是一个特殊的初始化进程
 */
static int
init_main(void *arg) {
    // 打印当前进程的pid和名称，用于调试和信息展示
    cprintf("this initproc, pid = %d, name = \"%s\"\n", current->pid, get_proc_name(current));
    
    // 打印传递给初始化进程的参数，这里假设参数是一个字符串
    cprintf("To U: \"%s\".\n", (const char *)arg);
    
    // 打印固定的告别信息，表示初始化进程即将结束
    cprintf("To U: \"en.., Bye, Bye. :)\"\n");
    return 0;
}

// proc_init - set up the first kernel thread idleproc "idle" by itself and 
//           - create the second kernel thread init_main
/**
 * proc_init函数是进程管理初始化的核心函数。
 * 它负责初始化进程列表、哈希表、空闲进程、以及创建初始化进程。
 */
void
proc_init(void) {
    int i;

    // 初始化全局进程列表
    list_init(&proc_list);

    // 初始化哈希列表，用于快速查找进程
    for (i = 0; i < HASH_LIST_SIZE; i ++) {
        list_init(hash_list + i);
    }

    // 分配空闲进程idleproc，这是系统中的第一个进程
    if ((idleproc = alloc_proc()) == NULL) {
        panic("cannot alloc idleproc.\n");
    }

    // 设置idleproc的基本信息
    idleproc->pid = 0;
    idleproc->state = PROC_RUNNABLE;
    idleproc->kstack = (uintptr_t)bootstack;
    idleproc->need_resched = 1;
    set_proc_name(idleproc, "idle");
    nr_process ++;

    // 将当前进程设置为idleproc
    current = idleproc;

    // 创建初始化进程init_main，这是系统中的第二个进程
    int pid = kernel_thread(init_main, "Hello world!!", 0);
    if (pid <= 0) {
        panic("create init_main failed.\n");
    }

    // 查找并设置初始化进程initproc
    initproc = find_proc(pid);
    set_proc_name(initproc, "init");

    // 断言确保idleproc和initproc正确初始化
    assert(idleproc != NULL && idleproc->pid == 0);
    assert(initproc != NULL && initproc->pid == 1);
}

// cpu_idle - at the end of kern_init, the first kernel thread idleproc will do below works
void
cpu_idle(void) {
    while (1) {
        //检查当前进程是否需要重新调度
        if (current->need_resched) {
            schedule();
        }
    }
}

